﻿using System.Collections.Generic;

namespace HazeCore.Persistence
{
    public static class OfflineListHelper
    {
        #region Nested types

        public interface IOrderedList<T> : IList<T>
        {
            int BinarySearch(T query, IComparer<T> comparer);

            List<T> GetRange(int index, int count);
            void RemoveRange(int index, int count);
            void AddRange(IEnumerable<T> items);
            void InsertRange(int index, IEnumerable<T> items);
        }

        /// <summary>
        ///  The interface whose instance represents a change to the underlying list
        /// </summary>
        /// <typeparam name="T">The type of the items in the list</typeparam>
        /// <remarks>
        ///  Three types of changes
        ///  1. Start less than End, non empty Items list: replacement
        ///  2. Start equal to End, non empty Items list: insertion
        ///  3. Start less than End, empty Items list: removal
        /// </remarks>
        public interface IChangeBlock<T>
        {
            #region Properties

            long Start { get; set; }
            long End { get; set; }

            long VirtualStart { get; set; }
            long VirtualEnd { get; }

            IOrderedList<T> Items { get; }

            bool IsDirty { get; set; }

            #endregion
        }

        public abstract class AbstractChangeBlock<T> : IChangeBlock<T>
        {
            public virtual long Start { get; set; }
            public virtual long End { get; set; }

            public virtual long VirtualStart { get; set; }
            public virtual long VirtualEnd
            {
                get { return VirtualStart + Items.Count; }
            }

            public abstract IOrderedList<T> Items { get; }

            public virtual bool IsDirty { get; set; } 
        }

        public sealed class QueryChangeBlock<T> : AbstractChangeBlock<T>
        {
            #region Properties

            public override long VirtualEnd
            {
                get { return _virtualEnd; }
            }

            public override IOrderedList<T> Items
            {
                get { /*never used*/return null; }
            }

            #endregion

            #region Constructors

            public QueryChangeBlock(long point)
            {
                VirtualStart = point;
                _virtualEnd = point + 1;
            }

            #endregion

            #region Fields

            private readonly long _virtualEnd;

            #endregion
        }

        /// <summary>
        ///  A change block comparer that assumes change blocks to compare don't overlap
        /// </summary>
        /// <typeparam name="T">The type of the items in the list change blocks are defined on</typeparam>
        public class ChangeBlockMutexComparer<T> : IComparer<IChangeBlock<T>>
        {
            #region Public fields

            public static ChangeBlockMutexComparer<T> Instance = new ChangeBlockMutexComparer<T>();

            #endregion

            #region Methods

            public int Compare(IChangeBlock<T> x, IChangeBlock<T> y)
            {
                if (x.VirtualEnd <= y.VirtualStart) return -1;
                return x.VirtualStart >= y.VirtualEnd ? 1 : 0;
            }

            #endregion
        }

        public interface IOfflineListOperator<T>
        {
            #region Properties

            IOrderedList<IChangeBlock<T>> Changes { get; }

            #endregion

            #region Methods

            /// <summary>
            ///  loads an object at the specified phyisical index
            /// </summary>
            /// <param name="index">The index at which the object is to be loaded</param>
            /// <returns>The loaded object</returns>
            T LoadAt(long index);

            IChangeBlock<T> CreateChangeBlock();

            #endregion
        }

        #endregion

        #region Methods

        public static int GetIncrement<T>(this IChangeBlock<T> changeBlock)
        {
            return (int)(changeBlock.Items.Count - (changeBlock.End - changeBlock.Start));
        }

        /// <summary>
        ///  Returns the index of the change block where the the item with the given index in the given list
        ///  is located or a negative value indicating where such a block should be inserted
        /// </summary>
        /// <typeparam name="T">The type of the items in the list</typeparam>
        /// <param name="list">The list that the helper is working on</param>
        /// <param name="index">The index of the item to query</param>
        /// <returns>The index fo the change block</returns>
        public static int GetChangeBlock<T>(this IOfflineListOperator<T> list, long index)
        {
            return list.Changes.BinarySearch(new QueryChangeBlock<T>(index), ChangeBlockMutexComparer<T>.Instance);
        }

        /// <summary>
        ///  Converts virtual index to the current physical index
        /// </summary>
        /// <typeparam name="T">The type of the items in the list</typeparam>
        /// <param name="list">The list that the helper is working on</param>
        /// <param name="idxVirtual">The virtual index to query</param>
        /// <returns>The physical index or a negative value indicating the index to the change block</returns>
        public static long VirtualToPhysical<T>(this IOfflineListOperator<T> list, long idxVirtual)
        {
            long physical;
            int idxChange;
            if (list.VirtualToPhysical(idxVirtual, out physical, out idxChange))
            {
                return physical;
            }
            return -idxChange - 1;
        }

        /// <summary>
        ///  
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        /// <param name="idxVirtual"></param>
        /// <param name="physical"></param>
        /// <param name="idxChange"></param>
        /// <returns></returns>
        public static bool VirtualToPhysical<T>(this IOfflineListOperator<T> list, long idxVirtual, out long physical, out int idxChange)
        {
            idxChange = list.GetChangeBlock(idxVirtual);
            if (idxChange >= 0)
            {
                physical = 0;    // the physical index is not cared about
                return false;
            }
            idxChange = -idxChange - 1;
            if (idxChange == 0)
            {
                physical = idxVirtual;
                return true;
            }
            // gets the change block before specified physical location
            var change = list.Changes[idxChange - 1];
            physical = change.End + idxVirtual - change.VirtualEnd;
            return true;
        }

        /// <summary>
        ///  Sets the value for the specified item in the list
        /// </summary>
        /// <typeparam name="T">The type of the items in the list</typeparam>
        /// <param name="list">The list that the helper is working on</param>
        /// <param name="index">The index of the item to set</param>
        /// <param name="value">The new value for the item</param>
        public static void SetItemAt<T>(this IOfflineListOperator<T> list, long index, T value)
        {
            var idxChange = list.GetChangeBlock(index);
            if (idxChange >= 0)
            {   // change block exists
                var change = list.Changes[idxChange];
                var offset = (int)(index - change.VirtualStart);
                change.Items[offset] = value;
                change.IsDirty = true;  // even if the value has changed
            }
            else
            {
                idxChange = -idxChange - 1;

                var prev = idxChange > 0 ? list.Changes[idxChange-1] : null;
                var next = idxChange < list.Changes.Count ? list.Changes[idxChange] : null;

                var mergePrev = (prev != null && prev.End == index);
                var mergeNext = (next != null && next.Start == index + 1);

                if (mergePrev && mergeNext)
                {   // join
                    prev.End = next.End;
                    prev.Items.Add(value);
                    prev.Items.AddRange(next.Items);
                    list.Changes.RemoveAt(idxChange);
                    prev.IsDirty = true;
                }
                else if (mergePrev)
                {
                    prev.End++;
                    prev.Items.Add(value);
                    prev.IsDirty = true;
                }
                else if (mergeNext)
                {
                    next.Start--;
                    next.Items.Insert(0, value);
                    next.IsDirty = true;
                }
                else
                {
                    var newChange = list.CreateChangeBlock();
                    newChange.Start = list.VirtualToPhysical(index);
                    newChange.VirtualStart = index;
                    newChange.Items.Add(value);
                    newChange.IsDirty = true;
                    list.Changes.Insert(idxChange, newChange);
                }
            }
        }

        /// <summary>
        ///  Gets the item at the specified position
        /// </summary>
        /// <typeparam name="T">The type of the items in the list</typeparam>
        /// <param name="list">The list that the helper is working on</param>
        /// <param name="index">The index of the item to get</param>
        /// <returns>The item to retrieve</returns>
        public static T GetItemAt<T>(this IOfflineListOperator<T> list, long index)
        {
            var physical = list.VirtualToPhysical(index);

            if (physical >= 0)
            {
                return list.LoadAt(physical);
            }
            var idxChange = (int)-physical-1;
            var change = list.Changes[idxChange];
            var offset = (int)(index - change.VirtualStart);
            return change.Items[offset];
        }

        public static void AddBlock<T>(this IOfflineListOperator<T> list, int index, IChangeBlock<T> change)
        {
            var mergeLeft = index > 0 && change.VirtualStart == list.Changes[index - 1].VirtualEnd;
            var mergeRight = index < list.Changes.Count - 1 && change.VirtualEnd == list.Changes[list.Changes.Count - 1].VirtualStart;
            if (mergeLeft && mergeRight)
            {
                var left = list.Changes[index - 1];
                var right = list.Changes[index];
                left.End = right.End;
                left.Items.AddRange(change.Items);
                left.Items.AddRange(right.Items);
                if (change.IsDirty || right.IsDirty)
                {
                    left.IsDirty = true;
                }
                list.Changes.RemoveAt(index);
            }
            else if (mergeLeft)
            {
                var left = list.Changes[index - 1];
                left.End = change.End;
                left.Items.AddRange(change.Items);
                if (change.IsDirty)
                {
                    left.IsDirty = true;
                }
            }
            else if (mergeRight)
            {
                var right = list.Changes[index];
                right.Start = change.Start;
                right.VirtualStart = change.VirtualStart;
                right.Items.InsertRange(0, change.Items);
            }
            else
            {
                list.Changes.Insert(index, change);    
            }
        }

        /// <summary>
        ///  Inserts items to the list
        /// </summary>
        /// <typeparam name="T">The type of the items in the list</typeparam>
        /// <param name="list">The list that the helper is working on</param>
        /// <param name="index">The index of the item before which the items are to insert</param>
        /// <param name="addend">The items to insert</param>
        public static void InsertRange<T>(this IOfflineListOperator<T> list, long index, IList<T> addend)
        {
            long physical;
            int idxChange;
            var onPhysical = list.VirtualToPhysical(index, out physical, out idxChange);

            if (!onPhysical)
            {
                var change = list.Changes[idxChange];
                var offset = (int)(index - change.VirtualStart);
                change.Items.InsertRange(offset, addend);
                change.IsDirty = true;
            }
            else
            {
                if (idxChange > 0 && list.Changes[idxChange - 1].VirtualEnd == index)
                {
                    var change = list.Changes[--idxChange];
                    change.Items.AddRange(addend);
                    change.IsDirty = true;
                }
                else
                {
                    var newChange = list.CreateChangeBlock();
                    newChange.End = newChange.Start = physical;
                    newChange.VirtualStart = index;
                    newChange.Items.AddRange(addend);
                    newChange.IsDirty = true;
                    list.Changes.Insert(idxChange, newChange);
                }
            }

            for (var i = idxChange + 1; i < list.Changes.Count; i++)
            {
                list.Changes[i].VirtualStart += addend.Count;
            }
        }

        /// <summary>
        ///  Removes items starting from specified index of specified number
        /// </summary>
        /// <typeparam name="T">The type of the items in the list</typeparam>
        /// <param name="list">The list that the helper is working on</param>
        /// <param name="index">The index starting from which the items to remove</param>
        /// <param name="count">The number of consecutive items to remove</param>
        public static void RemoveRange<T>(this IOfflineListOperator<T> list, long index, int count)
        {
            var indexLast = index + count;
            
            long? phy2 = null;
            long? phy1 = null;
            IChangeBlock<T> merged = null;
            int offset1;
            int offset2;

            int idx1;
            long phy1Val;
            if (list.VirtualToPhysical(index, out phy1Val, out idx1))
            {
                if (idx1 > 0 && list.Changes[idx1 - 1].End == phy1Val)
                {   // takes the node and keeps all of its contents
                    merged = list.Changes[--idx1];
                    offset1 = merged.Items.Count;
                }
                else
                {   // needs to take the succeeding node or create a new one and updates the physical starting point
                    offset1 = 0;
                    phy1 = phy1Val;
                }
            }
            else
            {   // takes the node and removes some of its items
                merged = list.Changes[idx1];
                offset1 = (int)(index - merged.VirtualStart);
            }

            int idx2;
            long phy2Val;
            if (list.VirtualToPhysical(indexLast, out phy2Val, out idx2))
            {
                if (phy2Val == list.Changes[idx2].Start)
                {   // takes the succeeding node and keeps everything in it
                    offset2 = 0;
                }
                else
                {   // takes the preceding node and removes everything from it and updates the phyiscal end point
                    idx2--; // doesn't matter if it's negative as in such case idx1 must be greater than idx2
                    offset2 = list.Changes[idx2].Items.Count;
                    phy2 = phy2Val;
                }
            }
            else
            {   // takes the node and keeps part of it;
                offset2 = (int)(indexLast - list.Changes[idx2].VirtualStart);
            }

            if (idx1 > idx2)
            {
                System.Diagnostics.Trace.Assert(phy1 != null && phy2 != null);
                merged = list.CreateChangeBlock();
                merged.Start = phy1.Value;
                merged.End = phy2.Value;
                merged.VirtualStart = index;
                merged.IsDirty = true;
                list.Changes.Insert(idx1, merged);
            }
            else
            {
                if (merged == null)
                {
                    System.Diagnostics.Trace.Assert(phy1 != null);
                    merged = list.Changes[idx1];
                    merged.Start = phy1.Value;
                    merged.VirtualStart = index;
                }
               
                var last = list.Changes[idx2];
                if (merged == last)
                {
                    if (offset1 < offset2)
                    {
                        merged.Items.RemoveRange(offset1, offset2 - offset1);
                    }
                }
                else
                {
                    if (offset1 < merged.Items.Count)
                    {
                        merged.Items.RemoveRange(offset1, merged.Items.Count - offset1);
                    }
                    merged.Items.AddRange(last.Items.GetRange(offset2, last.Items.Count - offset2));
                    list.Changes.RemoveRange(idx1 + 1, idx2 - idx1);
                }

                merged.End = phy2 != null ? phy2.Value : last.End;
                merged.IsDirty = true;
            }

            for (var i = idx1 + 1; i < list.Changes.Count; i++)
            {
                var change = list.Changes[i];
                change.VirtualStart -= count;
            }
        }

        #endregion
    }
}
